package org.test.algorithm;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class GeneticAlgorithm {
    private static final int POPULATION_SIZE = 100;
    private static final int CHROMOSOME_LENGTH = 10;
    private static final int MUTATION_RATE = (int) 0.01;
    private static final int NUM_GENERATIONS = 1000;
    private static final Random RANDOM = new Random();

    public static void main(String[] args) {
        List<Chromosome> population = initializePopulation();

        for (int generation = 0; generation < NUM_GENERATIONS; generation++) {
            evaluatePopulation(population);
            List<Chromosome> newPopulation = new ArrayList<>();

            // Selection
            List<Chromosome> selected = select(population);

            // Crossover and Mutation
            while (newPopulation.size() < POPULATION_SIZE) {
                Chromosome parent1 = selected.get(RANDOM.nextInt(selected.size()));
                Chromosome parent2 = selected.get(RANDOM.nextInt(selected.size()));
                Chromosome offspring = crossover(parent1, parent2);
                offspring = mutate(offspring);
                newPopulation.add(offspring);
            }

            population = newPopulation;

            // Optional: Print best individual of each generation
            Collections.sort(population, (c1, c2) -> Double.compare(c2.fitness, c1.fitness));
            System.out.println("Generation " + generation + ": Best fitness = " + population.get(0).fitness);
        }

        // Output the best solution found
        Collections.sort(population, (c1, c2) -> Double.compare(c2.fitness, c1.fitness));
        System.out.println("Best solution found: " + population.get(0).genes);
    }

    // Initialize population
    private static List<Chromosome> initializePopulation() {
        List<Chromosome> population = new ArrayList<>();
        for (int i = 0; i < POPULATION_SIZE; i++) {
            int[] genes = new int[CHROMOSOME_LENGTH];
            for (int j = 0; j < CHROMOSOME_LENGTH; j++) {
                genes[j] = RANDOM.nextInt(10); // Random integers between 0 and 9
            }
            double fitness = evaluateFitness(genes);
            population.add(new Chromosome(genes, fitness));
        }
        return population;
    }

    // Evaluate fitness of a chromosome
    private static double evaluateFitness(int[] genes) {
        int sum = 0;
        for (int gene : genes) {
            sum += gene;
        }
        return sum; // In this simple example, fitness is just the sum of the genes
    }

    // Evaluate fitness for the entire population
    private static void evaluatePopulation(List<Chromosome> population) {
        for (Chromosome chromosome : population) {
            chromosome.fitness = evaluateFitness(chromosome.genes);
        }
    }

    // Select individuals for mating based on their fitness
    private static List<Chromosome> select(List<Chromosome> population) {
        List<Chromosome> selected = new ArrayList<>();
        for (int i = 0; i < POPULATION_SIZE / 2; i++) {
            double totalFitness = population.stream().mapToDouble(c -> c.fitness).sum();
            double randomPoint = RANDOM.nextDouble() * totalFitness;
            double runningSum = 0;
            for (Chromosome chromosome : population) {
                runningSum += chromosome.fitness;
                if (runningSum >= randomPoint) {
                    selected.add(chromosome);
                    break;
                }
            }
            // To ensure we have unique parents, remove the selected individual from the pool
            // (this is a simplification and not strictly necessary in all genetic algorithms)
            population.remove(selected.get(selected.size() - 1));
        }
        // Restore the population for the next selection round (if needed)
        // In a real implementation, you might use a wheel selection, tournament selection, etc.
        // and avoid modifying the original population list during selection.
        // Here, we just re-create the original population list for simplicity.
        // Note: This part is incorrect for a real GA implementation and is just for demonstration.
        // In a correct implementation, you would maintain two separate lists: population and selected.
        // Or, you would use a selection method that doesn't require removing individuals from the population.
        // For now, we'll just re-initialize the population list after selection for simplicity.
        return initializePopulation(); // Incorrect! Just for demonstration purposes.
    }

    // Perform crossover between two parents to create an offspring
    private static Chromosome crossover(Chromosome parent1, Chromosome parent2) {
        int crossoverPoint = RANDOM.nextInt(CHROMOSOME_LENGTH);
        int[] offspringGenes = new int[CHROMOSOME_LENGTH];
        System.arraycopy(parent1.genes, 0, offspringGenes, 0, crossoverPoint);
        System.arraycopy(parent2.genes, crossoverPoint, offspringGenes, crossoverPoint, CHROMOSOME_LENGTH - crossoverPoint);
        double fitness = evaluateFitness(offspringGenes);
        return new Chromosome(offspringGenes, fitness);
    }

    // Mutate an individual's genes
    private static Chromosome mutate(Chromosome chromosome) {
        for (int i = 0; i < CHROMOSOME_LENGTH; i++) {
            if (RANDOM.nextDouble() < MUTATION_RATE) {
                chromosome.genes[i] = RANDOM.nextInt(10); // Random mutation to a new value between 0 and 9
            }
        }
        chromosome.fitness = evaluateFitness(chromosome.genes); // Recalculate fitness after mutation
        return chromosome;
    }

    // Chromosome class to hold gene sequence and fitness value
    static class Chromosome {
        int[] genes;
        double fitness;

        Chromosome(int[] genes, double fitness) {
            this.genes = genes;
            this.fitness = fitness;
        }
    }
}